# 1305 中等：两个二叉搜索树中的所有元素

# Definition for a binary tree node.
# class HOT.TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def getAllElements(self, root1: HOT.TreeNode, root2: HOT.TreeNode) -> List[int]:
        l = []

        def preOrder(root):
            if root is None:
                return
            l.append(root.val)
            preOrder(root.left)
            preOrder(root.right)

        preOrder(root1)
        list1 = l

        l = []
        preOrder(root2)
        list2 = l

        # print(list1, list2)

        list1.extend(list2)
        # print(list1)

        return sorted(list1)


# 中序排列+归并排序
# class Solution:
#     def getAllElements(self, root1: HOT.TreeNode, root2: HOT.TreeNode) -> List[int]:
#         def inorder(node: HOT.TreeNode, res: List[int]):
#             if node:
#                 inorder(node.left, res)
#                 res.append(node.val)
#                 inorder(node.right, res)
#
#         nums1, nums2 = [], []
#         inorder(root1, nums1)
#         inorder(root2, nums2)
#
#         merged = []
#         p1, n1 = 0, len(nums1)
#         p2, n2 = 0, len(nums2)
#         while True:
#             if p1 == n1:
#                 merged.extend(nums2[p2:])
#                 break
#             if p2 == n2:
#                 merged.extend(nums1[p1:])
#                 break
#             if nums1[p1] < nums2[p2]:
#                 merged.append(nums1[p1])
#                 p1 += 1
#             else:
#                 merged.append(nums2[p2])
#                 p2 += 1
#         return merged

